home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume18 / mtvraytrace / part01 next >
Encoding:
Internet Message Format  |  1989-03-26  |  58.1 KB
  1. Subject:  v18i070:  A ray-tracing package, Part01/03
  2. Newsgroups: comp.sources.unix
  3. Sender: sources
  4. Approved: rsalz@uunet.UU.NET
  5.  
  6. Submitted-by: Mark VandeWettering <markv@drizzle.cs.uoregon.edu>
  7. Posting-number: Volume 18, Issue 70
  8. Archive-name: mtvraytrace/part01
  9.  
  10. This represents the second formal release of the MTV Raytracer.  It was
  11. written to help me understand how raytracing works, to generate cute
  12. images, and generally because I like to program.  Feel free to use it for
  13. any purpose, I am releasing it into the public domain.
  14.  
  15. The input format to this ray tracer is called "NFF" or Neutral File
  16. Format, which was invented by Eric Haines' for his Standard Procedural
  17. Database.  The SPD was designed to allow programmers to test their
  18. raytracers on databases of varying sizes.  While not the end-all to object
  19. file formats, it has served me well.  If you wish to change the input file
  20. to something else, you probably only need to change the parser in
  21. "parse.y", not any of the other code.
  22.  
  23. #! /bin/sh
  24. # This is a shell archive.  Remove anything before this line, then unpack
  25. # it by saving it into a file and typing "sh file".  To overwrite existing
  26. # files, type "sh file -c".  You can also feed this as standard input via
  27. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  28. # will see the following message at the end:
  29. #        "End of archive 1 (of 3)."
  30. # Contents:  ALGORITHMS COPYING GETOPT INSTALL Makefile README
  31. #   antialiasing.c balls.nff bound.c config.h data.c defs.h error.c
  32. #   extern.h getopt.c main.c nff.y pic.c pic.h pqueue.c ray.1 sphere.c
  33. #   tokens.l trace.c vector.c
  34. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  35. if test -f 'ALGORITHMS' -a "${1}" != "-c" ; then 
  36.   echo shar: Will not clobber existing file \"'ALGORITHMS'\"
  37. else
  38. echo shar: Extracting \"'ALGORITHMS'\" \(1642 characters\)
  39. sed "s/^X//" >'ALGORITHMS' <<'END_OF_FILE'
  40. X
  41. X
  42. XThis should be more complete, but I really just wanted to point people at 
  43. Xthe papers that I used in creating this raytracer.  Much thanks to all the
  44. Xexcellent researchers and their papers, as well as the personal communications
  45. Xthat I have had.
  46. X
  47. XRay/Object Intersections:
  48. X
  49. XThe sphere code is almost identical to the code given in Heckbert's EXCELLENT
  50. Xarticle "Writing a Ray Tracer" in the Siggraph Course Notes.  Paul Heckbert 
  51. Xis to be commended on his excellent article.  The general structure of my 
  52. Xraytracer is closely modelled after his.
  53. X
  54. XPolygon intersections are modelled after the method described by Eric Haines 
  55. Xin his excellent paper, "Essential Algorithms for Ray Tracing", also in 
  56. Xthe Siggraph course notes.  Between these two papers, much of the drudgery of 
  57. Xdeveloping intersection code is removed.
  58. X
  59. XThe code for cone/cylinder intersections is fairly crude, but essentially my
  60. Xown derivation.  
  61. X
  62. XRay/Bounding Volume Intersections:
  63. X
  64. XRather than use octrees, I decided to use Kay/Kajiya bounding volumes, 
  65. Xas described in their 86 Siggraph paper, "Ray Tracing Complex Scenes".  Their
  66. Xmethod has proven to be fast and simple to implement.   The bounding volumes
  67. Xfor the cones and cylinders could be improved to provide a "tighter" bounding 
  68. Xvolume.
  69. X
  70. XI "discovered" simultaneously with Eric Haines through our conversations that
  71. Xwe could cheapen the cost of certain rays by establishing a max cutoff for 
  72. Xdistance during the Intersect() routine.  
  73. X
  74. XThe shadow caching optimization was introduced to me through conversations
  75. Xwith Eric Haines, although probably not original, and was quite simple to 
  76. Ximplement in my raytracer.
  77. END_OF_FILE
  78. if test 1642 -ne `wc -c <'ALGORITHMS'`; then
  79.     echo shar: \"'ALGORITHMS'\" unpacked with wrong size!
  80. fi
  81. # end of 'ALGORITHMS'
  82. fi
  83. if test -f 'COPYING' -a "${1}" != "-c" ; then 
  84.   echo shar: Will not clobber existing file \"'COPYING'\"
  85. else
  86. echo shar: Extracting \"'COPYING'\" \(574 characters\)
  87. sed "s/^X//" >'COPYING' <<'END_OF_FILE'
  88. X#
  89. X# MTV's RayTracer
  90. X#
  91. X# markv@cs.uoregon.edu
  92. X
  93. XThis program is public domain.  Feel free to modify it, hack it, use 
  94. Xit inside other programs, and even sell it.  I wrote it to better 
  95. Xunderstand raytracing and hope that it helps others understand the 
  96. Xraytracing process as well.
  97. X
  98. XShould you significantly extend my program, through bug fixes or additional
  99. Xfeatures, send the changes back to me for inclusion in later versions
  100. Xof the program.  I will try to make the latest version of my program 
  101. Xavailable via anonymous ftp from drizzle.cs.uoregon.edu.
  102. X
  103. XMark VandeWettering
  104. END_OF_FILE
  105. if test 574 -ne `wc -c <'COPYING'`; then
  106.     echo shar: \"'COPYING'\" unpacked with wrong size!
  107. fi
  108. # end of 'COPYING'
  109. fi
  110. if test -f 'GETOPT' -a "${1}" != "-c" ; then 
  111.   echo shar: Will not clobber existing file \"'GETOPT'\"
  112. else
  113. echo shar: Extracting \"'GETOPT'\" \(3178 characters\)
  114. sed "s/^X//" >'GETOPT' <<'END_OF_FILE'
  115. XDate: Tue, 25 Dec 84 19:20:50 EST
  116. XFrom: Keith Bostic <harvard!seismo!keith>
  117. XTo: genrad!sources
  118. XSubject: public domain getopt(3)
  119. X
  120. XThere have recently been several requests for a public
  121. Xdomain version of getopt(3), recently.  Thought this
  122. Xmight be worth reposting.
  123. X
  124. X        Keith Bostic
  125. X            ARPA: keith@seismo 
  126. X            UUCP: seismo!keith
  127. X
  128. X======================================================================
  129. XIn April of this year, Henry Spencer (utzoo!henry) released a public
  130. Xdomain version of getopt (USG, getopt(3)).  Well, I've been trying to
  131. Xport some USG dependent software and it didn't seem to work.  The problem
  132. Xended up being that the USG version of getopt has some external variables
  133. Xthat aren't mentioned in the documentation.  Anyway, to fix these problems,
  134. XI rewrote the public version of getopt.  It has the following advantages:
  135. X
  136. X    -- it includes those "unknown" variables
  137. X    -- it's smaller/faster 'cause it doesn't use the formatted
  138. X        output conversion routines in section 3 of the UNIX manual.
  139. X    -- the error messages are the same as S5's.
  140. X    -- it has the same side-effects that S5's has.
  141. X    -- the posted bug on how the error messages are flushed has been
  142. X        implemented.  (posting by Tony Hansen; pegasus!hansen)
  143. X
  144. XI won't post the man pages since Henry already did; a special note,
  145. Xit's not documented in the S5 manual that the options ':' and '?' are
  146. Xillegal.  It should be obvious, but I thought I'd mention it...
  147. XThis software was derived from binaries of S5 and the S5 man page, and is
  148. X(I think?) totally (I'm pretty sure?) compatible with S5 and backward
  149. Xcompatible to Henry's version.
  150. X
  151. X        Keith Bostic
  152. X            ARPA: keith@seismo 
  153. X            UUCP: seismo!keith
  154. X
  155. X*UNIX is a trademark of Bell Laboratories
  156. X
  157. X.. cut along the dotted line .........................................
  158. X
  159. X#include <stdio.h>
  160. X
  161. X/*
  162. X * get option letter from argument vector
  163. X */
  164. Xint    opterr = 1,        /* useless, never set or used */
  165. X    optind = 1,        /* index into parent argv vector */
  166. X    optopt;            /* character checked for validity */
  167. Xchar    *optarg;        /* argument associated with option */
  168. X
  169. X#define BADCH    (int)'?'
  170. X#define EMSG    ""
  171. X#define tell(s)    fputs(*nargv,stderr);fputs(s,stderr); \
  172. X        fputc(optopt,stderr);fputc('\n',stderr);return(BADCH);
  173. X
  174. Xgetopt(nargc,nargv,ostr)
  175. Xint    nargc;
  176. Xchar    **nargv,
  177. X    *ostr;
  178. X{
  179. X    static char    *place = EMSG;    /* option letter processing */
  180. X    register char    *oli;        /* option letter list index */
  181. X    char    *index();
  182. X
  183. X    if(!*place) {            /* update scanning pointer */
  184. X        if(optind >= nargc || *(place = nargv[optind]) != '-' || !*++place) return(EOF);
  185. X        if (*place == '-') {    /* found "--" */
  186. X            ++optind;
  187. X            return(EOF);
  188. X        }
  189. X    }                /* option letter okay? */
  190. X    if ((optopt = (int)*place++) == (int)':' || !(oli = index(ostr,optopt))) {
  191. X        if(!*place) ++optind;
  192. X        tell(": illegal option -- ");
  193. X    }
  194. X    if (*++oli != ':') {        /* don't need argument */
  195. X        optarg = NULL;
  196. X        if (!*place) ++optind;
  197. X    }
  198. X    else {                /* need an argument */
  199. X        if (*place) optarg = place;    /* no white space */
  200. X        else if (nargc <= ++optind) {    /* no arg */
  201. X            place = EMSG;
  202. X            tell(": option requires an argument -- ");
  203. X        }
  204. X         else optarg = nargv[optind];    /* white space */
  205. X        place = EMSG;
  206. X        ++optind;
  207. X    }
  208. X    return(optopt);            /* dump back option letter */
  209. X}
  210. X
  211. X
  212. X
  213. END_OF_FILE
  214. if test 3178 -ne `wc -c <'GETOPT'`; then
  215.     echo shar: \"'GETOPT'\" unpacked with wrong size!
  216. fi
  217. # end of 'GETOPT'
  218. fi
  219. if test -f 'INSTALL' -a "${1}" != "-c" ; then 
  220.   echo shar: Will not clobber existing file \"'INSTALL'\"
  221. else
  222. echo shar: Extracting \"'INSTALL'\" \(1170 characters\)
  223. sed "s/^X//" >'INSTALL' <<'END_OF_FILE'
  224. X
  225. XTo install the MTV raytracer is quite simple:
  226. X
  227. X1.    Edit config.h to indicate whether your computer understands void
  228. X    or not.  You might also have to define SYSV if you are running on 
  229. X    a SYSV system.
  230. X
  231. X2.    Check the Makefile.  The way it is currently distributed it is
  232. X    set up to run on suns with the 68881 processor, using the sun C 
  233. X    compiler.  If you have the gnu C compiler, uncomment the other
  234. X    set of CFLAGS and the definition of gcc as the C compiler.
  235. X
  236. X    You can expect much faster run times using gcc.  I have hacked in
  237. X    some assembler macros so it uses the 68881 for square roots inline,
  238. X    rather than calling the library function.  If you don't have gcc
  239. X    and are running on a sun, I urge you to get it.
  240. X
  241. X3.    Type make.  It should compile.
  242. X
  243. X4.    To test, try running it on the "balls.nff" file. 
  244. X
  245. X        balls -i balls.nff -o balls.pic -r 100 -t
  246. X    
  247. X5.    To display the image, you need to hack a filter to change it into
  248. X    a format your display device can understand.  The format is simple
  249. X    and described in the README.  Alternatively, you could ftp an 
  250. X    appropriate filter from drizzle.cs.uoregon.edu, where I try to keep
  251. X    an archive of filters that people have sent to me.   
  252. END_OF_FILE
  253. if test 1170 -ne `wc -c <'INSTALL'`; then
  254.     echo shar: \"'INSTALL'\" unpacked with wrong size!
  255. fi
  256. # end of 'INSTALL'
  257. fi
  258. if test -f 'Makefile' -a "${1}" != "-c" ; then 
  259.   echo shar: Will not clobber existing file \"'Makefile'\"
  260. else
  261. echo shar: Extracting \"'Makefile'\" \(2230 characters\)
  262. sed "s/^X//" >'Makefile' <<'END_OF_FILE'
  263. X#
  264. X# Makefile for Mark VandeWettering's 
  265. X# MTV RAYTRACER
  266. X#
  267. X
  268. XPROG=ray
  269. XCC=cc
  270. X#CC=gcc
  271. XCFLAGS=-f68881 -O
  272. X#CFLAGS=-DFAST_MATH_PRIMS -finline-functions -g -O
  273. X#CFLAGS=-m68000 -O -msoft-float
  274. XYFLAGS=-d
  275. X
  276. XCSRC=data.c main.c sphere.c vector.c shade.c trace.c intersect.c\
  277. X    screen.c pic.c poly.c bound.c error.c pqueue.c cone.c\
  278. X    color.c antialiasing.c tri.c getopt.c
  279. X
  280. XCOBJ=data.o main.o sphere.o vector.o shade.o trace.o intersect.o\
  281. X    screen.o pic.o poly.o bound.o error.o pqueue.o cone.o\
  282. X    color.o antialiasing.o tri.o getopt.o
  283. X
  284. XNFFFILES=balls.nff
  285. XDOCFILES=README ray.1 COPYING BIBLIO ALGORITHMS NFF GETOPT INSTALL
  286. XOSRC=nff.y tokens.l
  287. XOOBJ=nff.o tokens.o
  288. XHDRS=defs.h extern.h pic.h config.h
  289. XLIBS=-lm
  290. X
  291. X$(PROG):    $(COBJ) $(OOBJ)
  292. X    $(CC) $(CFLAGS) -o $(PROG) $(COBJ) $(OOBJ) $(LIBS)
  293. X
  294. Xclean:
  295. X    rm -f $(COBJ) $(OOBJ)
  296. X    rm -f core tags
  297. X
  298. X# This rule isn't guaranteed to work, it relies on gcc...
  299. X# to change in the final distributed version...
  300. X
  301. Xdepend:     $(CSRC) $(OSRC) $(HDR)
  302. X    sed '/^#DONT EDIT/,$$d' Makefile > Makefile.new
  303. X    echo "#DONT EDIT THIS, AUTOMATICALLY GENERATED#" >> Makefile.new
  304. X    $(CC) -MM $(CSRC) >> Makefile.new
  305. X    mv Makefile.new Makefile
  306. X
  307. Xlint:
  308. X    lint $(CSRC)
  309. X
  310. Xbackup:
  311. X    -mkdir .backup
  312. X    cp $(CSRC) $(OSRC) $(HDR) Makefile .backup
  313. X
  314. Xnewrevision:
  315. X    ci -t/dev/null $(CSRC) $(OSRC) Makefile ray.1 README $(HDRS)
  316. X
  317. Xkit:    $(CRSRC) $(OSRC) Makefile $(DOCFILES) $(NFFFILES) $(HDRS)
  318. X    rm -f Part*
  319. X    makekit $(CSRC) $(OSRC) Makefile $(DOCFILES) $(NFFFILES) $(HDRS)
  320. X
  321. X#DONT EDIT THIS, AUTOMATICALLY GENERATED#
  322. Xdata.o : data.c defs.h config.h 
  323. Xmain.o : main.c defs.h config.h extern.h 
  324. Xsphere.o : sphere.c defs.h config.h extern.h 
  325. Xvector.o : vector.c defs.h config.h extern.h 
  326. Xshade.o : shade.c defs.h config.h extern.h 
  327. Xtrace.o : trace.c defs.h config.h extern.h 
  328. Xintersect.o : intersect.c defs.h config.h extern.h 
  329. Xscreen.o : screen.c defs.h config.h pic.h extern.h 
  330. Xpic.o : pic.c pic.h defs.h config.h extern.h 
  331. Xpoly.o : poly.c defs.h config.h extern.h 
  332. Xbound.o : bound.c defs.h config.h extern.h 
  333. Xerror.o : error.c defs.h config.h extern.h 
  334. Xpqueue.o : pqueue.c defs.h config.h extern.h 
  335. Xcone.o : cone.c defs.h config.h extern.h 
  336. Xcolor.o : color.c defs.h config.h 
  337. Xantialiasing.o : antialiasing.c defs.h config.h 
  338. Xtri.o : tri.c defs.h config.h extern.h 
  339. END_OF_FILE
  340. if test 2230 -ne `wc -c <'Makefile'`; then
  341.     echo shar: \"'Makefile'\" unpacked with wrong size!
  342. fi
  343. # end of 'Makefile'
  344. fi
  345. if test -f 'README' -a "${1}" != "-c" ; then 
  346.   echo shar: Will not clobber existing file \"'README'\"
  347. else
  348. echo shar: Extracting \"'README'\" \(3205 characters\)
  349. sed "s/^X//" >'README' <<'END_OF_FILE'
  350. X########################################################################
  351. X              MTV RAYTRACER*
  352. X         written by Mark Terrence VandeWettering
  353. X              markv@cs.uoregon.edu
  354. X########################################################################
  355. X* Well, I have had the initials since 1964, Music Television can't say
  356. X  that :-)
  357. X
  358. XThis represents the second formal release of the MTV Raytracer.
  359. XIt was written to help me understand how raytracing works, to
  360. Xgenerate cute images, and generally because I like to program. 
  361. XFeel free to use it for any purpose, I am releasing it into the 
  362. Xpublic domain.
  363. X
  364. XThe input format to this ray tracer is called "NFF" or Neutral File
  365. XFormat, which was invented by Eric Haines' for his Standard Procedural
  366. XDatabase.  The SPD was designed to allow programmers to test their
  367. Xraytracers on databases of varying sizes.  While not the end-all to
  368. Xobject file formats, it has served me well.  If you wish to change the
  369. Xinput file to something else, you probably only need to change the
  370. Xparser in "parse.y", not any of the other code.
  371. X
  372. XNFF supports the following primitives:
  373. X    spheres
  374. X    cylinders
  375. X    cones
  376. X    polygons
  377. X    polygonal patches (normals are interpolated from corner points)
  378. X
  379. XThe MTV raytracer supports all of these primitives, with the minor
  380. Xlimitation that polygonal patches must be triangles (have only three
  381. Xvertices).  I am sure some clever person can convert patches with more
  382. Xsides to triangles, I haven't found the need yet.
  383. X
  384. XThe output from the raytracer is very simple, and not directly tied to
  385. Xany specific device.   It consists of a single line, with format in 
  386. XC scanf style of "%d %d\n", which gives the resolution of the image.
  387. XIt is then followed by x*y sets of (red green blue) bytes.  We have 
  388. Xpretty unstandard hardware here,  (I convert these to Utah Raster
  389. XToolkit form and then filter that to display on a Tek4115) but I do 
  390. Xmaintain an archive of source which has been sent to me for this
  391. Xpurpose.  More below--
  392. X
  393. XBy the time you read this, this raytracer should be available via
  394. Xanonymous ftp from drizzle.cs.uoregon.edu.  I will try to archive
  395. Xsource code for displaying the ".pic" files, as well as interesting
  396. Xobjects that I run accross.  Filters already exist to display images on
  397. Xsuns, to convert to PostScript and Impress, as well as X bitmaps Also
  398. Xavailable is Eric Haines' SPD source code, so you can generate your own
  399. Xfractal spheres, mountains, gears etc.
  400. X
  401. XBy placing this in the comp.sources.unix, I hope to get this to more of
  402. Xthe people who have requested it.  I will entertain e-mail with
  403. Xquestions, and even requests for the source code, but remember that I am
  404. Xa grad student only, and have limited time.  If it takes me a long time
  405. Xto reply, send mail to me again.
  406. X
  407. XThanks must go to Eric Haines especially, whose e-mail conversations
  408. Xhave been interesting and fruitful.  Also thanks to the numerous
  409. Xauthors whose research into raytracing has seen implementation in this
  410. Xraytracer, and have provided a host of ideas about image synthesis.
  411. XAlso thanks to Jeff Eaton and David Koblas, whose criticism and sense of
  412. Xcompetition drove this poor hacker to write a better program than he
  413. Xcould have without them.
  414. X
  415. XTa Ta For Now...
  416. XMark VandeWettering
  417. END_OF_FILE
  418. if test 3205 -ne `wc -c <'README'`; then
  419.     echo shar: \"'README'\" unpacked with wrong size!
  420. fi
  421. # end of 'README'
  422. fi
  423. if test -f 'antialiasing.c' -a "${1}" != "-c" ; then 
  424.   echo shar: Will not clobber existing file \"'antialiasing.c'\"
  425. else
  426. echo shar: Extracting \"'antialiasing.c'\" \(809 characters\)
  427. sed "s/^X//" >'antialiasing.c' <<'END_OF_FILE'
  428. X/***********************************************************************
  429. X * $Author: markv $
  430. X * $Revision: 1.1 $
  431. X * $Date: 88/09/17 01:10:52 $
  432. X * $Log:    antialiasing.c,v $
  433. X * Revision 1.1  88/09/17  01:10:52  markv
  434. X * Initial revision
  435. X * 
  436. X ***********************************************************************/
  437. X
  438. X#include <stdio.h>
  439. X#include <math.h>
  440. X#include "defs.h"
  441. X
  442. X/***********************************************************************
  443. X *
  444. X * Flt rnd() ;
  445. X *
  446. X * returns a (psuedo-)random number in the range 0-1.  This may
  447. X * not be portable, for now it assumes that random() returns an
  448. X * int in the range 0-(2^31-1).  Caveat Emptor!
  449. X ***********************************************************************/
  450. X
  451. X#define MAXRAND        (2147483647.0)
  452. X
  453. XFlt
  454. Xrnd ()
  455. X{
  456. X    return (((Flt) random ()) / ((Flt) MAXRAND));
  457. X}
  458. END_OF_FILE
  459. if test 809 -ne `wc -c <'antialiasing.c'`; then
  460.     echo shar: \"'antialiasing.c'\" unpacked with wrong size!
  461. fi
  462. # end of 'antialiasing.c'
  463. fi
  464. if test -f 'balls.nff' -a "${1}" != "-c" ; then 
  465.   echo shar: Will not clobber existing file \"'balls.nff'\"
  466. else
  467. echo shar: Extracting \"'balls.nff'\" \(558 characters\)
  468. sed "s/^X//" >'balls.nff' <<'END_OF_FILE'
  469. Xv
  470. Xfrom 2.1 1.3 0.0
  471. Xat 0 0 0
  472. Xup 0 1 1
  473. Xangle 45
  474. Xhither 1
  475. Xresolution 50 50
  476. Xb SkyBlue
  477. Xl 4 3 2
  478. Xl 1 -4 4
  479. Xl -3 1 5
  480. Xf yellow_green 1 0 0 0 0
  481. Xp 4
  482. X12 12 -.5
  483. X-12 12 -.5
  484. X-12 -12 -.5
  485. X12 -12 -.5
  486. Xf SteelBlue .5 .5 3 0 0
  487. Xs 0 0 0 .5
  488. Xs .272166 .272166 .544331 .166667
  489. Xs .643951 .172546 1.11022e-16 .166667
  490. Xs .172546 .643951 1.11022e-16 .166667
  491. Xs -.371785 0.0996195 .544331 .166667
  492. Xs -.471405 .471405 1.11022e-16 .166667
  493. Xs -.643951 -.172546 1.11022e-16 .166667
  494. Xs 0.0996195 -.371785 .544331 .166667
  495. Xs -.172546 -.643951 1.11022e-16 .166667
  496. Xs .471405 -.471405 1.11022e-16 .166667
  497. END_OF_FILE
  498. if test 558 -ne `wc -c <'balls.nff'`; then
  499.     echo shar: \"'balls.nff'\" unpacked with wrong size!
  500. fi
  501. # end of 'balls.nff'
  502. fi
  503. if test -f 'bound.c' -a "${1}" != "-c" ; then 
  504.   echo shar: Will not clobber existing file \"'bound.c'\"
  505. else
  506. echo shar: Extracting \"'bound.c'\" \(3724 characters\)
  507. sed "s/^X//" >'bound.c' <<'END_OF_FILE'
  508. X/***********************************************************************
  509. X * $Author: markv $
  510. X * $Revision: 1.3 $
  511. X * $Date: 88/10/31 14:47:22 $
  512. X * $Log:    bound.c,v $
  513. X * Revision 1.3  88/10/31  14:47:22  markv
  514. X * Removed the noisy printout which gave the bounds of the scene...
  515. X * 
  516. X * Revision 1.2  88/09/14  13:54:46  markv
  517. X * Check for overflow of array Prims[].  Should fix problems
  518. X * with rendering the gears at size factor 4.
  519. X * 
  520. X * Revision 1.1  88/09/11  11:00:36  markv
  521. X * Initial revision
  522. X * 
  523. X ***********************************************************************/
  524. X#include <stdio.h>
  525. X#include <math.h>
  526. X#include "defs.h"
  527. X#include "extern.h"
  528. X
  529. X/*
  530. X * This function attempts to use median cut
  531. X * to generate tighter bounding volumes than the old
  532. X * code...
  533. X */
  534. X
  535. XBuildBoundingSlabs()
  536. X{
  537. X    int low = 0 ;
  538. X    int high, i ;
  539. X
  540. X    high = nPrims ;
  541. X    while (SortAndSplit(low, high) == 0) {
  542. X        low = high ;
  543. X        high = nPrims ;
  544. X    }
  545. X    fprintf(stderr, "%s: after adding bounding volumes, %d prims\n",
  546. X        Progname, nPrims) ;
  547. X    fprintf(stderr, "%s: extent of scene\n", Progname) ;
  548. X#ifdef NOISY
  549. X    for (i = 0 ; i < NSLABS; i++) {
  550. X        fprintf(stderr, "%s: <%g -- %g>\n",
  551. X                Progname,
  552. X                Root -> o_dmin[i],
  553. X                Root -> o_dmax[i]) ;
  554. X    }
  555. X#endif /* NOISY */
  556. X}
  557. X
  558. Xstatic int Axis ;
  559. X
  560. Xint 
  561. Xcompslabs(a, b)
  562. X Object **a, **b ;
  563. X{
  564. X    Flt am, bm ;
  565. X
  566. X    am = (*a) -> o_dmin[Axis] + (*a) -> o_dmax[Axis] ;
  567. X    bm = (*b) -> o_dmin[Axis] + (*b) -> o_dmax[Axis] ;
  568. X
  569. X    if (am < bm)
  570. X        return (-1) ;
  571. X    else if (am == bm)
  572. X        return (0) ;
  573. X    else
  574. X        return (1) ;
  575. X}
  576. X
  577. Xint
  578. XFindAxis(first, last)
  579. X int first, last ;
  580. X{
  581. X    Flt    mins[NSLABS] ;
  582. X    Flt    maxs[NSLABS] ;
  583. X    int    i, j , which ;
  584. X    Flt     d = -HUGE, e ;
  585. X    for (i = 0 ; i < NSLABS ; i++) {
  586. X        mins[i] = HUGE ;
  587. X        maxs[i] = -HUGE ;
  588. X    }
  589. X
  590. X    for (i = first ; i < last ; i++) {
  591. X        for (j = 0 ; j < NSLABS ; j++) {
  592. X            if (Prims[i] -> o_dmin[j] < mins[j])
  593. X                mins[j] = Prims[i] -> o_dmin [j] ;
  594. X            if (Prims[i] -> o_dmin[j] > maxs[j])
  595. X                maxs[j] = Prims[i] -> o_dmax [j] ;
  596. X        }
  597. X    }
  598. X
  599. X    for (i = 0 ; i < NSLABS ; i++) {
  600. X        e = maxs[i] - mins[i] ;
  601. X        if (e > d) {
  602. X            d = e ;
  603. X            which = i ;
  604. X        }
  605. X    }
  606. X    return(which) ;
  607. X}
  608. X
  609. XSortAndSplit(first, last)
  610. X int first, last ;
  611. X{
  612. X    Object * cp ;
  613. X    CompositeData * cd ;
  614. X    int size, i, j ;
  615. X    Flt dmin, dmax ;
  616. X    int m ;
  617. X
  618. X    Axis = FindAxis(first, last) ;
  619. X
  620. X    size = last - first ;
  621. X
  622. X    /*
  623. X     * actually, we could do this faster in several ways.
  624. X     * we could use a logn algorithm to find the median
  625. X     * along the given axis, and then a linear algorithm to 
  626. X     * partition along the axis. Oh well...
  627. X     */
  628. X
  629. X    qsort((char *) (Prims + first), size, sizeof (Object *), compslabs) ;
  630. X
  631. X    if (size <= BUNCHINGFACTOR) {
  632. X        /* build a box to contain them */
  633. X
  634. X        cp = (Object *) malloc (sizeof(Object)) ;
  635. X        cp -> o_type = T_COMPOSITE ;
  636. X        cp -> o_procs = & NullProcs ;     /* die if you call any     */
  637. X        cp -> o_surf = NULL ;        /* no surface...    */
  638. X        cd = (CompositeData *) malloc (sizeof(CompositeData)) ;
  639. X        cd -> c_size = size ;
  640. X
  641. X        for(i = 0 ; i < size ; i++) {
  642. X            cd -> c_object[i] = Prims[first + i] ;
  643. X        }
  644. X
  645. X        for (i = 0 ; i < NSLABS ; i++ ) {
  646. X            dmin = HUGE ;
  647. X            dmax = -HUGE ;
  648. X            for (j = 0 ; j < size ; j++) {
  649. X                if (cd -> c_object[j] -> o_dmin[i] < dmin)
  650. X                    dmin = cd -> c_object[j] -> o_dmin[i] ;
  651. X                if (cd -> c_object[j] -> o_dmax[i] > dmax)
  652. X                    dmax = cd -> c_object[j] -> o_dmax[i] ;
  653. X            }
  654. X            cp -> o_dmin[i] = dmin ;
  655. X            cp -> o_dmax[i] = dmax ;
  656. X        }
  657. X        cp -> o_data = (void *) cd ;
  658. X        Root = cp ;
  659. X        if (nPrims < MAXPRIMS) {
  660. X            Prims[nPrims ++] = cp ;
  661. X            return (1) ;
  662. X        } else {
  663. X            fprintf(stderr, "too many primitives, max is %d\n",
  664. X                MAXPRIMS) ;
  665. X                exit(0);
  666. X        }
  667. X    } else {
  668. X        m = (first + last) / 2 ;
  669. X        SortAndSplit(first, m) ;
  670. X        SortAndSplit(m , last) ;
  671. X        return (0) ;
  672. X    }
  673. X}
  674. X    
  675. X
  676. XInitSlabs()
  677. X{
  678. X    int i ;
  679. X
  680. X    for (i = 0 ; i < NSLABS ; i ++) {
  681. X        VecNormalize(Slab[i]) ;
  682. X    }
  683. X}
  684. END_OF_FILE
  685. if test 3724 -ne `wc -c <'bound.c'`; then
  686.     echo shar: \"'bound.c'\" unpacked with wrong size!
  687. fi
  688. # end of 'bound.c'
  689. fi
  690. if test -f 'config.h' -a "${1}" != "-c" ; then 
  691.   echo shar: Will not clobber existing file \"'config.h'\"
  692. else
  693. echo shar: Extracting \"'config.h'\" \(1292 characters\)
  694. sed "s/^X//" >'config.h' <<'END_OF_FILE'
  695. X/***********************************************************************
  696. X * $Log:    config.h,v $
  697. X * Revision 1.2  88/09/12  13:02:06  markv
  698. X * Changed BUNCHINGFACTOR to something larger.
  699. X * Added defines for compilers which don't support void.
  700. X * Added a conditional define for SHADOW_CACHING
  701. X * 
  702. X * Revision 1.1  88/09/11  11:00:48  markv
  703. X * Initial revision
  704. X * 
  705. X ***********************************************************************/
  706. X
  707. X#ifdef SYS_V
  708. X#define index     strchr
  709. X#define rindex     strrchr
  710. X#endif /* SYS_V */
  711. X
  712. X#define        NSLABS        (3)
  713. X#define        BUNCHINGFACTOR    (4)
  714. X#define        PQSIZE        (100)
  715. X
  716. X#define        XMAX        (1024)
  717. X#define        YMAX        (1024)
  718. X#define        MAXLIGHTS    (10)
  719. X#define        MAXPRIMS    (40000)
  720. X#define        MAXLEVEL     (5)
  721. X
  722. X/***********************************************************************
  723. X * If your compiler doesn't grok the void type, then define NO_VOID
  724. X * here...
  725. X ***********************************************************************/
  726. X
  727. X/* #define NO_VOID */
  728. X#ifdef        NO_VOID
  729. X#define        void        char
  730. X#endif         /* NO_VOID */
  731. X
  732. X/***********************************************************************
  733. X * Shadow caching is an interesting optimization.  I'd leave it in, 
  734. X * I think it can really only help.
  735. X ***********************************************************************/
  736. X
  737. X#define SHADOW_CACHING
  738. END_OF_FILE
  739. if test 1292 -ne `wc -c <'config.h'`; then
  740.     echo shar: \"'config.h'\" unpacked with wrong size!
  741. fi
  742. # end of 'config.h'
  743. fi
  744. if test -f 'data.c' -a "${1}" != "-c" ; then 
  745.   echo shar: Will not clobber existing file \"'data.c'\"
  746. else
  747. echo shar: Extracting \"'data.c'\" \(1389 characters\)
  748. sed "s/^X//" >'data.c' <<'END_OF_FILE'
  749. X/***********************************************************************
  750. X * $Author: markv $
  751. X * $Revision: 1.3 $
  752. X * $Date: 88/09/17 01:23:10 $
  753. X * $Log:    data.c,v $
  754. X * Revision 1.3  88/09/17  01:23:10  markv
  755. X * Added definitions for antialias related variables
  756. X * 
  757. X * Revision 1.2  88/09/12  12:52:03  markv
  758. X * Added counter for shadow cache hits.  Made the max level of 
  759. X * recursion equal to the define MAXLEVEL in defs.h
  760. X * 
  761. X * Revision 1.1  88/09/11  11:02:13  markv
  762. X * Initial revision
  763. X * 
  764. X ***********************************************************************/
  765. X#include "defs.h"
  766. X
  767. Xint         yylinecount ;
  768. XViewpoint     Eye ;
  769. Xint         Xresolution = 512 ;
  770. Xint         Yresolution = 512 ;
  771. XLight        Lights[MAXLIGHTS] ;
  772. Xint        nLights = 0 ;
  773. XVec        BackgroundColor ;
  774. XSurface        * CurrentSurface ;
  775. XObject        * Prims[MAXPRIMS] ;
  776. Xint        nPrims = 0 ;
  777. XFlt        rayeps = 1e-6 ;
  778. Xchar *        Progname ;
  779. XObject        * Root ;
  780. X
  781. XFlt        minweight = 0.01 ;
  782. Xint        maxlevel = MAXLEVEL ;
  783. Xint        nRays = 0 ;
  784. Xint        nShadows = 0 ;
  785. Xint        nReflected = 0 ;
  786. Xint        nRefracted = 0 ;
  787. Xint        maxQueueSize = 0 ;
  788. Xint        totalQueues = 0 ;
  789. Xint        totalQueueResets = 0 ;
  790. Xint        tickflag = 0 ;
  791. Xint        filtflag = 0 ;
  792. Xint        jitterflag = 0 ;
  793. Xint        resolutionflag = 0 ;
  794. Xint        maxsamples = 0 ;
  795. Xint        nChecked = 0 ;
  796. Xint        nEnqueued = 0 ;
  797. Xint        nShadowCacheHits = 0 ;
  798. X
  799. XVec    Slab[] = {
  800. X    {1.0, 0.0, 0.0},
  801. X    {0.0, 1.0, 0.0},
  802. X    {0.0, 0.0, 1.0},
  803. X    {1.0, 1.0, 0.0},
  804. X    {1.0, 0.0, 1.0},
  805. X    {0.0, 1.0, 1.0}
  806. X} ;
  807. END_OF_FILE
  808. if test 1389 -ne `wc -c <'data.c'`; then
  809.     echo shar: \"'data.c'\" unpacked with wrong size!
  810. fi
  811. # end of 'data.c'
  812. fi
  813. if test -f 'defs.h' -a "${1}" != "-c" ; then 
  814.   echo shar: Will not clobber existing file \"'defs.h'\"
  815. else
  816. echo shar: Extracting \"'defs.h'\" \(4057 characters\)
  817. sed "s/^X//" >'defs.h' <<'END_OF_FILE'
  818. X/***********************************************************************
  819. X * $Log:    defs.h,v $
  820. X * Revision 1.4  88/10/06  12:54:57  markv
  821. X * I forgot (of course) that gcc runs on non-sun machines.  I have
  822. X * defined the FASTPRIMS so that if you are running a sun, you get them
  823. X * otherwise, you don't.
  824. X * 
  825. X * Revision 1.3  88/10/04  14:34:49  markv
  826. X * Added changes to allow for optimized CSG (courtesy of Glassner and
  827. X * Bronsvoort.
  828. X * 
  829. X * Revision 1.2  88/09/12  13:03:28  markv
  830. X * Added space in the Light structure for caching shadow objects.
  831. X * 
  832. X * Revision 1.1  88/09/11  11:00:49  markv
  833. X * Initial revision
  834. X * 
  835. X * Revision 1.1  88/09/09  11:59:55  markv
  836. X * Initial revision
  837. X * 
  838. X ***********************************************************************/
  839. X
  840. X#include "config.h"
  841. X
  842. Xtypedef double Flt ;
  843. Xtypedef Flt Vec[3] ;
  844. Xtypedef Vec Point ;
  845. Xtypedef Vec Color ;
  846. X
  847. X/*----------------------------------------------------------------------*/
  848. X
  849. X#ifndef DUMB_CPP 
  850. X
  851. X#define MakeVector(x, y, z, v)        (v)[0]=(x),(v)[1]=(y),(v)[2]=(z)
  852. X#define VecScale(S,a)    (a)[0] *= S ; (a)[1] *= S ; (a)[2] *= S
  853. X#define VecNegate(a)    (a)[0]=0-(a)[0];\
  854. X            (a)[1]=0-(a)[1];\
  855. X            (a)[2]=0-(a)[2];
  856. X#define VecDot(a,b)    ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
  857. X#define VecLen(a)    (sqrt(VecDot(a,a)))
  858. X#define VecCopy(a,b)     (b)[0]=(a)[0];(b)[1]=(a)[1];(b)[2]=(a)[2];
  859. X#define VecAdd(a,b,c)     (c)[0]=(a)[0]+(b)[0];\
  860. X             (c)[1]=(a)[1]+(b)[1];\
  861. X             (c)[2]=(a)[2]+(b)[2]
  862. X#define VecSub(a,b,c)     (c)[0]=(a)[0]-(b)[0];\
  863. X             (c)[1]=(a)[1]-(b)[1];\
  864. X             (c)[2]=(a)[2]-(b)[2]
  865. X#define VecComb(A,a,B,b,c)    (c)[0]=(A)*(a)[0]+(B)*(b)[0];\
  866. X                (c)[1]=(A)*(a)[1]+(B)*(b)[1];\
  867. X                 (c)[2]=(A)*(a)[2]+(B)*(b)[2]
  868. X#define VecAddS(A,a,b,c)     (c)[0]=(A)*(a)[0]+(b)[0];\
  869. X                 (c)[1]=(A)*(a)[1]+(b)[1];\
  870. X                 (c)[2]=(A)*(a)[2]+(b)[2]
  871. X#define VecCross(a,b,c)     (c)[0]=(a)[1]*(b)[2]-(a)[2]*(b)[1];\
  872. X             (c)[1]=(a)[2]*(b)[0]-(a)[0]*(b)[2];\
  873. X             (c)[2]=(a)[0]*(b)[1]-(a)[1]*(b)[0]
  874. X#define VecPrint(msg,v)        printf("%s %g %g %g\n", msg,\
  875. X                    (v)[0],(v)[1],(v)[2])
  876. X#define VecZero(v)    (v)[0]=0.0;(v)[1]=0.0;v[2]=0.0
  877. X
  878. X#endif /* not DUMB_CPP */
  879. X
  880. X/*----------------------------------------------------------------------*/
  881. X
  882. Xtypedef struct Ray {
  883. X    Point P ;
  884. X    Point D ;
  885. X} Ray ;
  886. X
  887. X#define RayPoint(ray,t,point)    VecAddS(t,(ray)->D,(ray)->P,point)
  888. X
  889. X#define max(a,b)     ((a)>(b)?(a):(b))
  890. X#define min(a,b)     ((a)<(b)?(a):(b))
  891. X
  892. X/*----------------------------------------------------------------------*/
  893. X
  894. Xtypedef struct t_surface {
  895. X    Color    surf_color ;
  896. X    Flt    surf_kd ;
  897. X    Flt    surf_ks ;
  898. X    Flt    surf_shine ;
  899. X    Flt     surf_kt ;
  900. X    Flt    surf_ior ;
  901. X} Surface ;
  902. X
  903. Xtypedef struct t_light {
  904. X    Vec    light_pos ;
  905. X    Flt    light_brightness ;
  906. X    struct t_object * light_obj_cache[MAXLEVEL] ;
  907. X} Light ;
  908. X
  909. Xtypedef struct t_viewpoint {
  910. X    Vec    view_from ;
  911. X    Vec    view_at ;
  912. X    Vec    view_up ;
  913. X    Flt    view_angle ;
  914. X    Flt    view_dist ;
  915. X} Viewpoint ;
  916. X
  917. Xtypedef struct t_object {
  918. X    unsigned short     o_type ;
  919. X    Flt    o_dmin[NSLABS] ;
  920. X    Flt    o_dmax[NSLABS] ;
  921. X    struct t_objectprocs {
  922. X        int     (*print) () ;
  923. X        int     (*intersect) () ;
  924. X        int     (*normal) () ;
  925. X    } * o_procs ;
  926. X    struct t_surface     * o_surf ;
  927. X    struct t_object        * o_parent ;
  928. X    unsigned short        * o_inside ;
  929. X    void    * o_data ;
  930. X} Object ;
  931. X
  932. Xtypedef struct t_compositedata {
  933. X    unsigned short     c_size ;
  934. X    Object *    c_object[BUNCHINGFACTOR] ;
  935. X} CompositeData ;
  936. X
  937. Xtypedef struct t_objectprocs ObjectProcs ;
  938. X
  939. Xtypedef struct t_isect {
  940. X    Flt         isect_t ;
  941. X    int         isect_enter ;
  942. X    Vec        isect_normal ;
  943. X    Object         * isect_prim ;
  944. X    Surface     * isect_surf ;
  945. X} Isect ;
  946. X
  947. Xtypedef struct t_pixel {
  948. X    unsigned char r, g, b, q ;
  949. X} Pixel ;
  950. X
  951. X#ifndef PI
  952. X#define PI         (3.14159265358979323844)
  953. X#endif /* PI */
  954. X
  955. X#define degtorad(x)    (((Flt)(x))*PI/180.0)
  956. X
  957. X#define        T_COMPOSITE    (0)
  958. X#define        T_SPHERE    (1)
  959. X#define        T_POLY        (2)
  960. X#define        T_CONE        (3)
  961. X#define        T_CONE        (3)
  962. X#define        T_TRI        (4)
  963. X
  964. X#ifdef __GNUC__
  965. X#define INLINE    inline
  966. X
  967. X#if defined(FAST_MATH_PRIMS) && defined(sun)
  968. X#define sqrt(x)\
  969. X    ({ double __value, __arg = (x) ;\
  970. X     asm("fsqrtx %1,%0": "=f" (__value): "f" (__arg)) ;\
  971. X     __value ;})
  972. X#endif /* FAST_MATH_PRIMS */
  973. X
  974. X#else /* __GNUC__ */
  975. X
  976. X#define INLINE    /* inline not supported  */
  977. X
  978. X#endif /* __GNUC__ */
  979. END_OF_FILE
  980. if test 4057 -ne `wc -c <'defs.h'`; then
  981.     echo shar: \"'defs.h'\" unpacked with wrong size!
  982. fi
  983. # end of 'defs.h'
  984. fi
  985. if test -f 'error.c' -a "${1}" != "-c" ; then 
  986.   echo shar: Will not clobber existing file \"'error.c'\"
  987. else
  988. echo shar: Extracting \"'error.c'\" \(878 characters\)
  989. sed "s/^X//" >'error.c' <<'END_OF_FILE'
  990. X/***********************************************************************
  991. X * $Author: markv $
  992. X * $Revision: 1.1 $
  993. X * $Date: 88/09/11 11:00:39 $
  994. X * $Log:    error.c,v $
  995. X * Revision 1.1  88/09/11  11:00:39  markv
  996. X * Initial revision
  997. X * 
  998. X ***********************************************************************/
  999. X#include <stdio.h>
  1000. X#include <math.h>
  1001. X#include "defs.h"
  1002. X#include "extern.h"
  1003. X
  1004. X/*
  1005. X * various routines to print error messages and die...
  1006. X */
  1007. X
  1008. Xint NullPrint() ;
  1009. Xint NullIntersect() ;
  1010. Xint NullNormal() ;
  1011. X
  1012. XObjectProcs NullProcs = {
  1013. X    NullPrint,
  1014. X    NullIntersect,
  1015. X    NullNormal
  1016. X} ;
  1017. X
  1018. XNullPrint()
  1019. X{
  1020. X    fprintf(stderr, "%s: called (* print)(...), dying...\n", Progname) ;
  1021. X    abort() ;
  1022. X}
  1023. X
  1024. XNullIntersect()
  1025. X{
  1026. X    fprintf(stderr, "%s: called (* intersect)(...), dying...\n", Progname) ;
  1027. X    abort() ;
  1028. X}
  1029. X
  1030. XNullNormal()
  1031. X{
  1032. X    fprintf(stderr, "%s: called (* normal)(...), dying...\n", Progname) ;
  1033. X    abort() ;
  1034. X}
  1035. END_OF_FILE
  1036. if test 878 -ne `wc -c <'error.c'`; then
  1037.     echo shar: \"'error.c'\" unpacked with wrong size!
  1038. fi
  1039. # end of 'error.c'
  1040. fi
  1041. if test -f 'extern.h' -a "${1}" != "-c" ; then 
  1042.   echo shar: Will not clobber existing file \"'extern.h'\"
  1043. else
  1044. echo shar: Extracting \"'extern.h'\" \(1787 characters\)
  1045. sed "s/^X//" >'extern.h' <<'END_OF_FILE'
  1046. X/***********************************************************************
  1047. X * $Log:    extern.h,v $
  1048. X * Revision 1.3  88/09/17  01:22:05  markv
  1049. X * Added definitions for new antialiasing variables, plus
  1050. X * function definitions for functions which return the chi-squared
  1051. X * values.
  1052. X * 
  1053. X * Revision 1.2  88/09/12  13:11:13  markv
  1054. X * Added extern definition for nShadowCacheHits
  1055. X * 
  1056. X * Revision 1.1  88/09/11  11:00:49  markv
  1057. X * Initial revision
  1058. X * 
  1059. X ***********************************************************************/
  1060. Xextern  int         yylinecount ;
  1061. Xextern    Viewpoint     Eye ;
  1062. Xextern    int         Xresolution ;
  1063. Xextern    int         Yresolution ;
  1064. Xextern    Light        Lights[] ;
  1065. Xextern    int        nLights ;
  1066. Xextern    Vec        BackgroundColor ;
  1067. Xextern    Surface        * CurrentSurface ;
  1068. Xextern    Object        * Prims[] ;
  1069. Xextern    int        nPrims ;
  1070. Xextern     Flt        rayeps ;
  1071. Xextern    char *        Progname ;
  1072. Xextern     int        maxQueueSize ;
  1073. Xextern     int        totalQueues ;
  1074. Xextern    int        totalQueueResets ;
  1075. Xextern     int        tickflag ;
  1076. Xextern     int        filtflag ;
  1077. Xextern     int        jitterflag ;
  1078. Xextern     int        resolutionflag ;
  1079. Xextern  int        nChecked ;
  1080. Xextern     int        nEnqueued ;
  1081. Xextern  int        nShadowCacheHits ;
  1082. X
  1083. Xextern     Flt        minweight ;
  1084. Xextern     int        maxlevel ;
  1085. Xextern    int        maxsamples ;
  1086. Xextern    Flt        variance ;
  1087. Xextern  Flt        maxerror ;
  1088. Xextern     int        nRays ;
  1089. Xextern    int        nShadows ;
  1090. Xextern    int        nReflected ;
  1091. Xextern     int        nRefracted ;
  1092. X
  1093. Xchar *        malloc() ;
  1094. Xchar *        calloc() ;
  1095. Xchar *        rindex() ;
  1096. X
  1097. Xextern    Object *    MakeCone() ;
  1098. Xextern    Object *    MakeSphere() ;
  1099. Xextern    Object *    MakePatch() ;
  1100. Xextern    Object *    MakePoly() ;
  1101. Xextern    Object *     MakeTri() ;
  1102. X
  1103. Xextern     Flt        VecNormalize() ;
  1104. Xextern     Flt        rnd() ;
  1105. Xextern    Flt        critchisq() ;
  1106. Xextern    Flt        pochisq() ;
  1107. Xextern    Vec        Slab[] ;
  1108. Xextern    ObjectProcs    NullProcs ;
  1109. Xextern     Object *    Root ;
  1110. X
  1111. X#ifdef DUMB_CPP
  1112. X
  1113. Xextern Flt    VecDot() ;
  1114. Xextern Flt     VecLen() ;
  1115. X
  1116. X#endif /* DUMB_CPP */
  1117. END_OF_FILE
  1118. if test 1787 -ne `wc -c <'extern.h'`; then
  1119.     echo shar: \"'extern.h'\" unpacked with wrong size!
  1120. fi
  1121. # end of 'extern.h'
  1122. fi
  1123. if test -f 'getopt.c' -a "${1}" != "-c" ; then 
  1124.   echo shar: Will not clobber existing file \"'getopt.c'\"
  1125. else
  1126. echo shar: Extracting \"'getopt.c'\" \(1407 characters\)
  1127. sed "s/^X//" >'getopt.c' <<'END_OF_FILE'
  1128. X
  1129. X#include <stdio.h>
  1130. X
  1131. X/*
  1132. X * get option letter from argument vector
  1133. X */
  1134. Xint    opterr = 1,        /* useless, never set or used */
  1135. X    optind = 1,        /* index into parent argv vector */
  1136. X    optopt;            /* character checked for validity */
  1137. Xchar    *optarg;        /* argument associated with option */
  1138. X
  1139. X#define BADCH    (int)'?'
  1140. X#define EMSG    ""
  1141. X#define tell(s)    fputs(*nargv,stderr);fputs(s,stderr); \
  1142. X        fputc(optopt,stderr);fputc('\n',stderr);return(BADCH);
  1143. X
  1144. Xgetopt(nargc,nargv,ostr)
  1145. Xint    nargc;
  1146. Xchar    **nargv,
  1147. X    *ostr;
  1148. X{
  1149. X    static char    *place = EMSG;    /* option letter processing */
  1150. X    register char    *oli;        /* option letter list index */
  1151. X    char    *index();
  1152. X
  1153. X    if(!*place) {            /* update scanning pointer */
  1154. X        if(optind >= nargc || *(place = nargv[optind]) != '-' || !*++place) return(EOF);
  1155. X        if (*place == '-') {    /* found "--" */
  1156. X            ++optind;
  1157. X            return(EOF);
  1158. X        }
  1159. X    }                /* option letter okay? */
  1160. X    if ((optopt = (int)*place++) == (int)':' || !(oli = index(ostr,optopt))) {
  1161. X        if(!*place) ++optind;
  1162. X        tell(": illegal option -- ");
  1163. X    }
  1164. X    if (*++oli != ':') {        /* don't need argument */
  1165. X        optarg = NULL;
  1166. X        if (!*place) ++optind;
  1167. X    }
  1168. X    else {                /* need an argument */
  1169. X        if (*place) optarg = place;    /* no white space */
  1170. X        else if (nargc <= ++optind) {    /* no arg */
  1171. X            place = EMSG;
  1172. X            tell(": option requires an argument -- ");
  1173. X        }
  1174. X         else optarg = nargv[optind];    /* white space */
  1175. X        place = EMSG;
  1176. X        ++optind;
  1177. X    }
  1178. X    return(optopt);            /* dump back option letter */
  1179. X}
  1180. END_OF_FILE
  1181. if test 1407 -ne `wc -c <'getopt.c'`; then
  1182.     echo shar: \"'getopt.c'\" unpacked with wrong size!
  1183. fi
  1184. # end of 'getopt.c'
  1185. fi
  1186. if test -f 'main.c' -a "${1}" != "-c" ; then 
  1187.   echo shar: Will not clobber existing file \"'main.c'\"
  1188. else
  1189. echo shar: Extracting \"'main.c'\" \(3268 characters\)
  1190. sed "s/^X//" >'main.c' <<'END_OF_FILE'
  1191. X/***********************************************************************
  1192. X * $Author: markv $
  1193. X * $Revision: 1.6 $
  1194. X * $Date: 88/10/31 14:33:44 $
  1195. X * $Log:    main.c,v $
  1196. X * Revision 1.6  88/10/31  14:33:44  markv
  1197. X * Removed non-functioning antialiasing...
  1198. X * 
  1199. X * Revision 1.5  88/10/04  14:29:16  markv
  1200. X * Added flags having to do with antialiasing, both statistically
  1201. X * optimized and jittered.
  1202. X * 
  1203. X * Revision 1.4  88/09/13  16:08:21  markv
  1204. X * Moved InitSlabs, must occur before ReadSceneFile
  1205. X * 
  1206. X * Revision 1.3  88/09/13  16:05:44  markv
  1207. X * Usage message now prints -t flag as well.
  1208. X * 
  1209. X * Revision 1.2  88/09/12  12:53:11  markv
  1210. X * Added printout of new statistic on shadow cache hits.
  1211. X * 
  1212. X * Revision 1.1  88/09/11  11:02:23  markv
  1213. X * Initial revision
  1214. X * 
  1215. X ***********************************************************************/
  1216. X
  1217. X#include <stdio.h>
  1218. X#include <sys/types.h>
  1219. X#include <sys/times.h>
  1220. X#include "defs.h"
  1221. X#include "extern.h"
  1222. X
  1223. Xmain(argc, argv)
  1224. X int argc ;
  1225. X char * argv[] ;
  1226. X{
  1227. X    extern int optind ;
  1228. X    extern char *optarg ;
  1229. X    int c ;
  1230. X    char * infilename = NULL ;
  1231. X    char * outfilename = "out.pic" ;
  1232. X    struct tms pbuf, tbuf ;
  1233. X
  1234. X    if ((Progname = rindex(argv[0], '/')) == NULL) 
  1235. X        Progname = argv[0] ;
  1236. X    else 
  1237. X        Progname ++ ;
  1238. X
  1239. X    while ((c = getopt(argc, argv, "r:a:o:i:tfj:")) != EOF) {
  1240. X        switch (c) {
  1241. X        case 'r':
  1242. X            resolutionflag = atoi(optarg) ;
  1243. X            break ;
  1244. X        case 'f':
  1245. X            filtflag = 1 ;
  1246. X            break ;
  1247. X        case 'j':
  1248. X            jitterflag = 1 ;
  1249. X            maxsamples = atoi(optarg) ;
  1250. X            if (maxsamples <= 0) {
  1251. X                fprintf(stderr, "%s: samples must be > 0\n",
  1252. X                    Progname) ;
  1253. X                exit(1) ;
  1254. X            }
  1255. X            break ;
  1256. X        case 'o':
  1257. X            outfilename = optarg ;
  1258. X            break ;
  1259. X        case 'i':
  1260. X            infilename = optarg ;
  1261. X            break ;
  1262. X        case 't':
  1263. X            tickflag = 1 ;
  1264. X            break ;
  1265. X        case '?':
  1266. X            fprintf(stderr, "usage: %s [-i file] [-o file] [-t]\n",
  1267. X                Progname) ;
  1268. X            exit(-1);
  1269. X        }
  1270. X    }
  1271. X
  1272. X    InitSlabs() ;            /* Normalizes slab normals...    */
  1273. X    ReadSceneFile(infilename) ;
  1274. X    if (resolutionflag > 0) {
  1275. X        Xresolution = Yresolution = resolutionflag ;
  1276. X    }
  1277. X    BuildBoundingSlabs() ;
  1278. X    times(&pbuf) ;
  1279. X    Screen(&Eye, outfilename, Xresolution, Yresolution) ;
  1280. X    times(&tbuf) ;
  1281. X    tbuf.tms_utime -= pbuf.tms_utime ;
  1282. X    tbuf.tms_stime -= pbuf.tms_stime ;
  1283. X    PrintStatistics(&pbuf, &tbuf) ;
  1284. X}
  1285. X
  1286. XPrintStatistics(pbuf, tbuf)
  1287. X struct tms *pbuf, *tbuf ;
  1288. X{
  1289. X
  1290. X    printf("preprocess time (user code)    %-6d seconds\n",
  1291. X            pbuf -> tms_utime / 60) ;
  1292. X    printf("preprocess time (system code)    %-6d seconds\n",
  1293. X            pbuf -> tms_stime / 60) ;
  1294. X    printf("tracing time (user code)    %-6d seconds\n",
  1295. X            tbuf -> tms_utime / 60 ) ;
  1296. X    printf("tracing time (system code)    %-6d seconds\n",
  1297. X            tbuf -> tms_stime / 60 ) ;
  1298. X
  1299. X    printf("number of rays cast:       %-6d\n", nRays);
  1300. X    printf("number of shadow rays:       %-6d\n", nShadows);
  1301. X    printf("number of reflected rays:  %-6d\n", nReflected);
  1302. X    printf("number of refracted rays:  %-6d\n", nRefracted);
  1303. X
  1304. X    printf("number of queue inserts:   %-6d\n", totalQueues) ;
  1305. X    printf("number of queue resets:    %-6d\n", totalQueueResets) ;
  1306. X    printf("avg number of queues/ray:  %-6g\n", (Flt) totalQueues /
  1307. X                        (Flt) totalQueueResets) ;
  1308. X    printf("max queue size:           %-6d\n", maxQueueSize) ;
  1309. X    printf("number of bound checks:       %-6d\n", nChecked) ;
  1310. X    printf("number of bound queued:       %-6d\n", nEnqueued) ;
  1311. X    printf("number of shadow hits:       %-6d\n", nShadowCacheHits) ;
  1312. X}
  1313. END_OF_FILE
  1314. if test 3268 -ne `wc -c <'main.c'`; then
  1315.     echo shar: \"'main.c'\" unpacked with wrong size!
  1316. fi
  1317. # end of 'main.c'
  1318. fi
  1319. if test -f 'nff.y' -a "${1}" != "-c" ; then 
  1320.   echo shar: Will not clobber existing file \"'nff.y'\"
  1321. else
  1322. echo shar: Extracting \"'nff.y'\" \(3873 characters\)
  1323. sed "s/^X//" >'nff.y' <<'END_OF_FILE'
  1324. X%{
  1325. X#include <stdio.h>
  1326. X#include <math.h>
  1327. X#include "defs.h"
  1328. X#include "extern.h"
  1329. X
  1330. Xextern char yytext[] ;
  1331. Xextern FILE * yyin ;
  1332. XVec * pl, * plist ;
  1333. X%}
  1334. X
  1335. X%token VIEWPOINT FROM AT UP ANGLE HITHER RESOLUTION LIGHT
  1336. X%token BACKGROUND SURFACE CONE SPHERE POLYGON PATCH NUM TOKEN
  1337. X
  1338. X%union {
  1339. X    Vec    vec ;
  1340. X    Vec *    vecl ;
  1341. X    double    flt ;
  1342. X    Object * obj ;
  1343. X} ;
  1344. X
  1345. X%type <vec>    point primcolor TOKEN
  1346. X%type <obj>    cone sphere polygon ppatch
  1347. X%type <flt>    num 
  1348. X
  1349. X%%
  1350. X
  1351. Xscene:
  1352. X    camera elementlist 
  1353. X    {
  1354. X        int i, l ;
  1355. X        for (l = 0 ; l < nLights ; l++) {
  1356. X            Lights[l].light_brightness =  sqrt((Flt) nLights) / 
  1357. X                            ((Flt)nLights) ;
  1358. X            for (i = 0 ; i < MAXLEVEL ; i++) {
  1359. X                Lights[l].light_obj_cache[i] = NULL ;
  1360. X            }
  1361. X        }
  1362. X    } ;
  1363. X
  1364. Xelementlist:
  1365. X    elementlist element
  1366. X    |  ;
  1367. X
  1368. Xelement:
  1369. X    light
  1370. X    | background
  1371. X    | surface
  1372. X    | object 
  1373. X    {
  1374. X        char buf[80] ;
  1375. X        if (nPrims >= MAXPRIMS) {
  1376. X            sprintf(buf, "max objects = %d", MAXPRIMS) ;
  1377. X            yyerror(buf) ;
  1378. X        }
  1379. X    }    ;
  1380. X
  1381. Xobject:      cone
  1382. X    | sphere
  1383. X    | polygon
  1384. X    | ppatch ;
  1385. X
  1386. Xcamera:
  1387. X    VIEWPOINT            /* $1      */
  1388. X    FROM point            /* $2-$3   */
  1389. X    AT point            /* $4-$5   */
  1390. X    UP point            /* $6-$7   */
  1391. X    ANGLE num             /* $8-$9   */
  1392. X    HITHER num            /* $10-$11 */
  1393. X    RESOLUTION num num        /* $12-$14 */
  1394. X    {
  1395. X        VecCopy($3, Eye.view_from) ;
  1396. X        VecCopy($5, Eye.view_at) ;
  1397. X        VecCopy($7, Eye.view_up) ;
  1398. X        Eye.view_angle = degtorad($9/2.0 ) ;
  1399. X        Eye.view_dist = $11 ;
  1400. X        if (resolutionflag > 0) {
  1401. X            /* ignore the specified resolution... */
  1402. X            Xresolution = Yresolution = resolutionflag ;
  1403. X        } else {
  1404. X            Xresolution = (int) $13 ;
  1405. X            Yresolution = (int) $14 ;
  1406. X        }
  1407. X    } ;
  1408. X
  1409. Xlight:
  1410. X    LIGHT point 
  1411. X    {
  1412. X        VecCopy($2, Lights[nLights].light_pos) ;
  1413. X        /* fill in brightness of the light, after we 
  1414. X         * know the number of lights sources in the scene
  1415. X         */
  1416. X        nLights ++ ;
  1417. X    } ;
  1418. X
  1419. Xbackground:
  1420. X    BACKGROUND primcolor
  1421. X    {
  1422. X        VecCopy($2, BackgroundColor) ;
  1423. X    } ;
  1424. X
  1425. Xsurface:
  1426. X    SURFACE primcolor num num num num num 
  1427. X    {
  1428. X        CurrentSurface = (Surface *) malloc (sizeof(Surface)) ;
  1429. X        VecCopy($2, CurrentSurface -> surf_color) ;
  1430. X        CurrentSurface -> surf_kd = $3 ;
  1431. X        CurrentSurface -> surf_ks = $4 ;
  1432. X        CurrentSurface -> surf_shine = $5 ;
  1433. X        CurrentSurface -> surf_kt = $6 ;
  1434. X        CurrentSurface -> surf_ior = $7 ;
  1435. X    } ;
  1436. X
  1437. Xcone:
  1438. X    CONE point num point num 
  1439. X    {
  1440. X        $$ = MakeCone($2, $3, $4, $5) ;
  1441. X        Prims[nPrims++] = $$ ;
  1442. X
  1443. X    } ;
  1444. Xsphere:
  1445. X    SPHERE point num 
  1446. X    {
  1447. X        $$ = MakeSphere($2, $3) ;
  1448. X        Prims[nPrims++] = $$ ;
  1449. X    } ;
  1450. X
  1451. Xpolygon:
  1452. X    POLYGON num 
  1453. X    {
  1454. X        plist = (Vec *) calloc((int) $2, sizeof(Vec)) ;
  1455. X        pl = plist ;
  1456. X    } 
  1457. X    pointlist 
  1458. X    {
  1459. X        $$ = MakePoly((int) $2, plist) ;
  1460. X        Prims[nPrims++] = $$ ;
  1461. X    } ;
  1462. Xppatch:
  1463. X    PATCH num
  1464. X        {
  1465. X        if ((int) $2 != 3)
  1466. X            fprintf(stderr, "patches must have 3 vertices...\n") ;
  1467. X        plist = (Vec *) calloc(2 * (int) $2, sizeof(Vec)) ;
  1468. X        pl = plist ;
  1469. X    }
  1470. X    pointlist
  1471. X    {
  1472. X        $$ = MakeTri(plist) ;
  1473. X        Prims[nPrims++] = $$ ;
  1474. X    } ;
  1475. X
  1476. Xprimcolor:
  1477. X    num num num 
  1478. X    {
  1479. X        $$[0] = $1 ;
  1480. X        $$[1] = $2 ;
  1481. X        $$[2] = $3 ;
  1482. X    }  
  1483. X    | TOKEN
  1484. X    {
  1485. X        char buf[80] ;
  1486. X
  1487. X        if (LookupColorByName(yytext, $$) == 0) {
  1488. X            sprintf(buf, "cannot find color \"%s\"\n",
  1489. X                yytext) ;
  1490. X            yyerror(buf) ;
  1491. X        }
  1492. X    } ;
  1493. X
  1494. Xpoint:
  1495. X    num num num
  1496. X    {
  1497. X        $$[0] = $1 ;
  1498. X        $$[1] = $2 ;
  1499. X        $$[2] = $3 ;
  1500. X    } ;
  1501. X
  1502. Xpointlist:
  1503. X    pointlist point
  1504. X    {
  1505. X        VecCopy($2, (*pl)) ;
  1506. X        pl ++ ;
  1507. X    } 
  1508. X    | ;
  1509. X
  1510. Xnum:
  1511. X    NUM
  1512. X        {
  1513. X            $$ = atof(yytext) ;
  1514. X        } ;
  1515. X
  1516. X%%
  1517. X
  1518. Xyyerror(str)
  1519. X char * str ;
  1520. X{
  1521. X    fprintf(stderr, "%s: error at line %d\n", 
  1522. X        Progname, yylinecount) ;
  1523. X    fprintf(stderr, "%s: %s\n", Progname, str) ;
  1524. X    exit(-1) ;
  1525. X}
  1526. X
  1527. XReadSceneFile(str)
  1528. X char *str ;
  1529. X{
  1530. X    if (str == NULL) 
  1531. X        yyin = stdin ;
  1532. X    else {
  1533. X        if ((yyin = fopen(str, "r")) == NULL) {
  1534. X            fprintf(stderr, "%s: cannot open %s\n", Progname,
  1535. X                        str) ;
  1536. X            exit(-1) ;
  1537. X        }
  1538. X    }
  1539. X    if (yyparse() == 1) {
  1540. X        fprintf(stderr, "%s: invalid input specification\n", Progname);
  1541. X        exit(-1) ;
  1542. X    }
  1543. X    fprintf(stderr, "%s: %d prims, %d lights\n", 
  1544. X            Progname, nPrims, nLights) ;
  1545. X    fprintf(stderr, "%s: inputfile = \"%s\"\n", Progname, str) ;
  1546. X    fprintf(stderr, "%s: resolution %dx%d\n", Progname, Xresolution,
  1547. X        Yresolution) ;
  1548. X}
  1549. END_OF_FILE
  1550. if test 3873 -ne `wc -c <'nff.y'`; then
  1551.     echo shar: \"'nff.y'\" unpacked with wrong size!
  1552. fi
  1553. # end of 'nff.y'
  1554. fi
  1555. if test -f 'pic.c' -a "${1}" != "-c" ; then 
  1556.   echo shar: Will not clobber existing file \"'pic.c'\"
  1557. else
  1558. echo shar: Extracting \"'pic.c'\" \(1689 characters\)
  1559. sed "s/^X//" >'pic.c' <<'END_OF_FILE'
  1560. X/***********************************************************************
  1561. X * $Author: markv $
  1562. X * $Revision: 1.2 $
  1563. X * $Date: 88/10/04 14:30:44 $
  1564. X * $Log:    pic.c,v $
  1565. X * Revision 1.2  88/10/04  14:30:44  markv
  1566. X * Changed pixel writing primitives to write individual pixels rather
  1567. X * than scanlines.  Simplifies certain loops inside Screen.
  1568. X * 
  1569. X * Revision 1.1  88/09/11  11:00:41  markv
  1570. X * Initial revision
  1571. X * 
  1572. X ***********************************************************************/
  1573. X
  1574. X#include <stdio.h>
  1575. X#include "pic.h"
  1576. X#include "defs.h"
  1577. X#include "extern.h"
  1578. X
  1579. X/*======================================================================*/
  1580. X/* PIC.C                                */
  1581. X/*                                                                      */
  1582. X/* Simple routines for outputting a pixel map....                       */
  1583. X/*                                                                      */
  1584. X/* Mark VandeWettering, markv@cs.uoregon.edu                            */
  1585. X/*======================================================================*/
  1586. X
  1587. XPic *
  1588. XPicOpen(filename,x,y)
  1589. X char *filename ;
  1590. X{
  1591. X    Pic    *tmp ;
  1592. X
  1593. X    tmp = (Pic *) malloc(sizeof (Pic)) ;
  1594. X    tmp -> filename = (char *) malloc (strlen(filename)+1) ;
  1595. X    strcpy(tmp->filename, filename);
  1596. X
  1597. X    if (((tmp -> filep)=fopen(filename, "w"))==NULL) {
  1598. X        perror( filename );
  1599. X        exit( 1 );
  1600. X    }
  1601. X
  1602. X    tmp -> x = x ; tmp -> y = y ;
  1603. X
  1604. X    fprintf(tmp -> filep, "%d %d\n", x, y);
  1605. X
  1606. X    return(tmp);
  1607. X}
  1608. X
  1609. XPicWritePixel(pic, color)
  1610. X Pic *pic ;
  1611. X Color color ;
  1612. X{
  1613. X    fputc((unsigned char) (255.0 * color[0]), pic -> filep) ;
  1614. X    fputc((unsigned char) (255.0 * color[1]), pic -> filep) ;
  1615. X    fputc((unsigned char) (255.0 * color[2]), pic -> filep) ;
  1616. X}
  1617. X
  1618. XPicClose(pic)
  1619. X Pic *pic ;
  1620. X{
  1621. X    fclose(pic -> filep) ;
  1622. X}
  1623. END_OF_FILE
  1624. if test 1689 -ne `wc -c <'pic.c'`; then
  1625.     echo shar: \"'pic.c'\" unpacked with wrong size!
  1626. fi
  1627. # end of 'pic.c'
  1628. fi
  1629. if test -f 'pic.h' -a "${1}" != "-c" ; then 
  1630.   echo shar: Will not clobber existing file \"'pic.h'\"
  1631. else
  1632. echo shar: Extracting \"'pic.h'\" \(376 characters\)
  1633. sed "s/^X//" >'pic.h' <<'END_OF_FILE'
  1634. X/***********************************************************************
  1635. X * $Log:    pic.h,v $
  1636. X * Revision 1.1  88/09/11  11:00:50  markv
  1637. X * Initial revision
  1638. X * 
  1639. X * Revision 1.1  88/09/09  11:59:56  markv
  1640. X * Initial revision
  1641. X * 
  1642. X ***********************************************************************/
  1643. Xtypedef struct Pic {
  1644. X    char    * filename ;
  1645. X    FILE    * filep ;
  1646. X    int    x, y ;
  1647. X} Pic ;
  1648. END_OF_FILE
  1649. if test 376 -ne `wc -c <'pic.h'`; then
  1650.     echo shar: \"'pic.h'\" unpacked with wrong size!
  1651. fi
  1652. # end of 'pic.h'
  1653. fi
  1654. if test -f 'pqueue.c' -a "${1}" != "-c" ; then 
  1655.   echo shar: Will not clobber existing file \"'pqueue.c'\"
  1656. else
  1657. echo shar: Extracting \"'pqueue.c'\" \(1818 characters\)
  1658. sed "s/^X//" >'pqueue.c' <<'END_OF_FILE'
  1659. X/***********************************************************************
  1660. X * $Author: markv $
  1661. X * $Revision: 1.1 $
  1662. X * $Date: 88/09/11 11:00:42 $
  1663. X * $Log:    pqueue.c,v $
  1664. X * Revision 1.1  88/09/11  11:00:42  markv
  1665. X * Initial revision
  1666. X * 
  1667. X ***********************************************************************/
  1668. X
  1669. X#include <stdio.h>
  1670. X#include <math.h>
  1671. X#include "defs.h"
  1672. X#include "extern.h"
  1673. X
  1674. Xtypedef struct t_qelem {
  1675. X    Flt    q_key ;
  1676. X    Object    * q_obj ;
  1677. X} Qelem ;
  1678. X
  1679. Xstatic int     Qsize ;
  1680. Xstatic Qelem    Q[PQSIZE] ;
  1681. X
  1682. XPriorityQueueNull()
  1683. X{
  1684. X    Qsize = 0 ;
  1685. X    totalQueueResets ++ ;
  1686. X#ifdef DEBUG    
  1687. X    printf("resetting\n") ;
  1688. X#endif /* DEBUG */
  1689. X}
  1690. X
  1691. XPriorityQueueEmpty()
  1692. X{
  1693. X    return (Qsize == 0) ;
  1694. X}
  1695. X
  1696. XPriorityQueueInsert(key, obj)
  1697. X Flt key ;
  1698. X Object * obj ;
  1699. X{
  1700. X    int i ; 
  1701. X    Qelem tmp ;
  1702. X
  1703. X    totalQueues ++ ;
  1704. X#ifdef DEBUG
  1705. X    printf("inserting element, key = %g\n", key) ;
  1706. X#endif
  1707. X     Qsize ++ ;
  1708. X    if (Qsize > maxQueueSize)
  1709. X        maxQueueSize = Qsize ;
  1710. X    if (Qsize >= PQSIZE) {
  1711. X        fprintf(stderr, "%s: exhausted priority queue space\n", 
  1712. X            Progname) ;
  1713. X        exit(1) ;
  1714. X    }
  1715. X    Q[Qsize].q_key = key ;
  1716. X    Q[Qsize].q_obj = obj ;
  1717. X
  1718. X    i = Qsize ;
  1719. X    while (i > 1 && Q[i].q_key < Q[i/2].q_key) {
  1720. X        tmp = Q[i] ;
  1721. X        Q[i] = Q[i/2] ;
  1722. X        Q[i/2] = tmp ;
  1723. X        i = i / 2 ;
  1724. X    }
  1725. X}
  1726. X
  1727. XPriorityQueueDelete(key, obj)
  1728. X Flt * key ;
  1729. X Object ** obj ;
  1730. X{
  1731. X    Qelem tmp ;
  1732. X    int i, j ;
  1733. X
  1734. X    if (Qsize == 0) {
  1735. X        fprintf(stderr, "%s: priority queue is empty\n",
  1736. X            Progname) ;
  1737. X        exit(1) ;
  1738. X    }
  1739. X
  1740. X    *key = Q[1].q_key ;
  1741. X    *obj = Q[1].q_obj ;
  1742. X
  1743. X#ifdef DEBUG
  1744. X    printf("deleting element, key = %g\n", *key) ;
  1745. X#endif
  1746. X
  1747. X    Q[1] = Q[Qsize] ;
  1748. X    Qsize -- ;
  1749. X
  1750. X    i = 1 ;
  1751. X
  1752. X    while (2 * i <= Qsize) {
  1753. X
  1754. X        if (2 * i == Qsize) {
  1755. X            j = 2 * i ;
  1756. X        } else if (Q[2*i].q_key < Q[2*i+1].q_key) {
  1757. X            j = 2 * i ;
  1758. X        } else {
  1759. X            j = 2 * i + 1 ;
  1760. X        }
  1761. X
  1762. X        if (Q[i].q_key > Q[j].q_key) {
  1763. X            tmp = Q[i] ;
  1764. X            Q[i] = Q[j] ;
  1765. X            Q[j] = tmp ;
  1766. X            i = j ;
  1767. X        } else {
  1768. X            break ;
  1769. X        }
  1770. X    }
  1771. X}
  1772. END_OF_FILE
  1773. if test 1818 -ne `wc -c <'pqueue.c'`; then
  1774.     echo shar: \"'pqueue.c'\" unpacked with wrong size!
  1775. fi
  1776. # end of 'pqueue.c'
  1777. fi
  1778. if test -f 'ray.1' -a "${1}" != "-c" ; then 
  1779.   echo shar: Will not clobber existing file \"'ray.1'\"
  1780. else
  1781. echo shar: Extracting \"'ray.1'\" \(2127 characters\)
  1782. sed "s/^X//" >'ray.1' <<'END_OF_FILE'
  1783. X.\" Copyright 1988, Mark VandeWettering
  1784. X.\" This program and documentation may be distributed freely for
  1785. X.\" any use whatsoever...
  1786. X.TH RAY 1 "August 17, 1987" 1
  1787. X.UC 4 
  1788. X.SH NAME
  1789. Xray \- a reasonbly intelligent ray tracing program
  1790. X.SH SYNOPSIS
  1791. X.B progname
  1792. X.\" sample options...
  1793. X[
  1794. X.B \-i inputfile
  1795. X] [
  1796. X.B \-o outputfile
  1797. X] [
  1798. X.B \-t 
  1799. X] [
  1800. X.B \-j # of samples
  1801. X] [
  1802. X.B \-f
  1803. X] [
  1804. X.B \-r resolution
  1805. X]
  1806. X.SH DESCRIPTION
  1807. XThis program is an attempt at writing a reasonably useful
  1808. Xraytracer for further experimentation, and for generating some
  1809. Xgenerally nifty pictures.  
  1810. X.PP
  1811. XIt reads Eric Haine's NFF file format files as input.  NFF is fairly
  1812. Xstraightforward, if you desire more explanation on the format, then 
  1813. Xobtain his set of routines.  They are available for download via anonymous
  1814. Xftp from drizzle.cs.uoregon.edu (128.223.4.1) in the pub subdirectory.
  1815. X.PP
  1816. XThe
  1817. X.B \-t
  1818. Xflag makes the ray tracer output a period after every scanline for those
  1819. Xof you who get impatient, or who are wondering if it is still working.
  1820. X.PP
  1821. XUse
  1822. X.B \-i file
  1823. Xto specify an NFF input file to render.  If no input file is specified, 
  1824. Xit reads from standard input.
  1825. X.PP
  1826. XUse
  1827. X.B \-o file
  1828. Xto specify an output file.  If unspecified, the raytracer writes its image
  1829. Xon the file "out.pic".
  1830. X.PP
  1831. XNormally the raytracer performs no antialiasing.  Images tend to look choppy.
  1832. XA cheap but imperfect solution is to specify the
  1833. X.B \-f 
  1834. Xflag, which tells the raytracer to make the pixel value the average of the 
  1835. Xfour pixels.  A more expensive but nicer way to antialias is to use the 
  1836. X.B \-j #samples
  1837. Xflag.  This uses jittered sampling to determine the value of a pixel, with 
  1838. Xa constant number of samples per pixel.  A pretty good value for the number
  1839. Xof samples is sixteen, but the image will take sixteen times as long to render.
  1840. X.PP
  1841. XThe 
  1842. X.B \-r 
  1843. Xflag allows you to override the resolution which is specified
  1844. Xfrom within the NFF file.   It is often useful when you don't
  1845. Xwant to edit the NFF file to get a more or less detailed image
  1846. Xthan you specified in the file.
  1847. X
  1848. X.SH AUTHOR
  1849. XMark VandeWettering
  1850. X.SH BUGS
  1851. XBugs!  Of course there are bugs!  Report them to markv@cs.uoregon.edu....
  1852. END_OF_FILE
  1853. if test 2127 -ne `wc -c <'ray.1'`; then
  1854.     echo shar: \"'ray.1'\" unpacked with wrong size!
  1855. fi
  1856. # end of 'ray.1'
  1857. fi
  1858. if test -f 'sphere.c' -a "${1}" != "-c" ; then 
  1859.   echo shar: Will not clobber existing file \"'sphere.c'\"
  1860. else
  1861. echo shar: Extracting \"'sphere.c'\" \(2385 characters\)
  1862. sed "s/^X//" >'sphere.c' <<'END_OF_FILE'
  1863. X/***********************************************************************
  1864. X * $Author: markv $
  1865. X * $Revision: 1.1 $
  1866. X * $Date: 88/09/11 11:00:44 $
  1867. X * $Log:    sphere.c,v $
  1868. X * Revision 1.1  88/09/11  11:00:44  markv
  1869. X * Initial revision
  1870. X * 
  1871. X ***********************************************************************/
  1872. X
  1873. X#include <stdio.h>
  1874. X#include <math.h>
  1875. X#include "defs.h"
  1876. X#include "extern.h"
  1877. X
  1878. Xtypedef struct t_spheredata {
  1879. X    Vec         sph_center ;
  1880. X    Flt         sph_radius ;
  1881. X    Flt         sph_radius2 ;
  1882. X} SphereData ;
  1883. X
  1884. Xint SpherePrint ();
  1885. Xint SphereIntersect ();
  1886. Xint SphereNormal ();
  1887. X
  1888. XObjectProcs SphereProcs = {
  1889. X    SpherePrint,
  1890. X    SphereIntersect,
  1891. X    SphereNormal,
  1892. X} ;
  1893. X
  1894. Xint 
  1895. XSpherePrint(obj)
  1896. X Object *obj ;
  1897. X{
  1898. X    SphereData * sp ;
  1899. X
  1900. X    sp = (SphereData *) obj -> o_data ;
  1901. X
  1902. X    printf("s %g %g %g %g\n", sp -> sph_center[0], 
  1903. X                   sp -> sph_center[1],
  1904. X                   sp -> sph_center[2],
  1905. X                   sp -> sph_radius) ;
  1906. X}
  1907. X
  1908. XSphereIntersect(obj, ray, hit)
  1909. X Object * obj ;
  1910. X Ray * ray ;
  1911. X Isect * hit ;
  1912. X{
  1913. X
  1914. X    Flt b, disc, t;
  1915. X    Point V ;
  1916. X    SphereData * sp ;
  1917. X
  1918. X    sp = (SphereData *) obj -> o_data ;
  1919. X
  1920. X    VecSub((sp->sph_center), ray -> P, V);
  1921. X
  1922. X    b = VecDot(V, ray -> D);
  1923. X
  1924. X    disc = b * b - VecDot(V, V) + (sp -> sph_radius2) ;
  1925. X
  1926. X    if (disc < 0.0)
  1927. X        return(0);
  1928. X
  1929. X    disc = sqrt(disc);
  1930. X
  1931. X    t = (b - disc < rayeps) ? b + disc : b - disc ;
  1932. X
  1933. X    if (t < rayeps) {
  1934. X        return(0);
  1935. X    }
  1936. X
  1937. X    hit -> isect_t = t ;
  1938. X    hit -> isect_enter = VecDot(V, V) > sp -> sph_radius2 + rayeps ? 1 : 0 ;
  1939. X    hit -> isect_prim = obj ;
  1940. X    hit -> isect_surf = obj -> o_surf ;
  1941. X    return (1);
  1942. X}
  1943. X
  1944. Xint
  1945. XSphereNormal(obj, hit, P, N)
  1946. X Object * obj ;
  1947. X Isect * hit ;
  1948. X Point P, N ;
  1949. X{
  1950. X    SphereData * sp ;
  1951. X    sp = (SphereData *) obj -> o_data ;
  1952. X
  1953. X    VecSub(P, sp -> sph_center, N);
  1954. X    (void) VecNormalize(N);
  1955. X}
  1956. X
  1957. XObject *
  1958. XMakeSphere(pos, radius)
  1959. X Vec pos ;
  1960. X Flt radius ;
  1961. X{
  1962. X    Object * tmp ;
  1963. X    int i ;
  1964. X    SphereData *sp ;
  1965. X
  1966. X    tmp = (Object *) malloc (sizeof(Object)) ;
  1967. X    tmp -> o_type = T_SPHERE ;
  1968. X    tmp -> o_procs = & SphereProcs ;
  1969. X    tmp -> o_surf = CurrentSurface ;
  1970. X    sp = (SphereData *) malloc (sizeof(SphereData)) ;
  1971. X    VecCopy(pos, sp -> sph_center) ;
  1972. X    sp -> sph_radius = radius ;
  1973. X    sp -> sph_radius2 = radius * radius ;
  1974. X    tmp -> o_data = (void *) sp ;
  1975. X
  1976. X    /*
  1977. X     * figure out dmin and dmax values for 
  1978. X     * each of the slabs...
  1979. X     */
  1980. X    
  1981. X    for (i = 0 ; i < NSLABS; i ++) {
  1982. X        tmp -> o_dmin[i] = VecDot(sp -> sph_center, Slab[i]) 
  1983. X            - sp -> sph_radius ;
  1984. X        tmp -> o_dmax[i] = VecDot(sp -> sph_center, Slab[i]) 
  1985. X            + sp -> sph_radius ;
  1986. X    }
  1987. X    return tmp ;
  1988. X}
  1989. END_OF_FILE
  1990. if test 2385 -ne `wc -c <'sphere.c'`; then
  1991.     echo shar: \"'sphere.c'\" unpacked with wrong size!
  1992. fi
  1993. # end of 'sphere.c'
  1994. fi
  1995. if test -f 'tokens.l' -a "${1}" != "-c" ; then 
  1996.   echo shar: Will not clobber existing file \"'tokens.l'\"
  1997. else
  1998. echo shar: Extracting \"'tokens.l'\" \(768 characters\)
  1999. sed "s/^X//" >'tokens.l' <<'END_OF_FILE'
  2000. X%{
  2001. X#include <stdio.h>
  2002. X#include "defs.h"
  2003. X#include "y.tab.h"
  2004. X#include "extern.h"
  2005. X%}
  2006. X
  2007. X%%
  2008. X[ \t]            ;
  2009. X\#.*$            ;
  2010. X\n            yylinecount ++ ;
  2011. Xv            return VIEWPOINT ;
  2012. Xviewpoint        return VIEWPOINT ;
  2013. Xfrom            return FROM ;
  2014. Xat            return AT ;
  2015. Xup            return UP ;
  2016. Xangle            return ANGLE ;
  2017. Xhither            return HITHER ;
  2018. Xresolution        return RESOLUTION ;
  2019. Xl            return LIGHT ;
  2020. Xlight            return LIGHT ;
  2021. Xb            return BACKGROUND ;
  2022. Xbackground        return BACKGROUND ;
  2023. Xf            return SURFACE ;
  2024. Xsurface            return SURFACE ;
  2025. Xc            return CONE ;
  2026. Xcone            return CONE ;
  2027. Xs            return SPHERE ;
  2028. Xsphere            return SPHERE ;
  2029. Xp            return POLYGON ;
  2030. Xpolygon            return POLYGON ;
  2031. Xpp            return PATCH ;
  2032. Xpatch            return PATCH ;
  2033. X\-?[0-9]*(\.[0-9]*(e\-?[0-9]+)?)?     return NUM ;
  2034. X[A-Za-z0-9_]+        return TOKEN ;
  2035. X.            return yytext[0] ;
  2036. X
  2037. X%%
  2038. X
  2039. Xyywrap()
  2040. X{
  2041. X    return 1 ;
  2042. X}
  2043. END_OF_FILE
  2044. if test 768 -ne `wc -c <'tokens.l'`; then
  2045.     echo shar: \"'tokens.l'\" unpacked with wrong size!
  2046. fi
  2047. # end of 'tokens.l'
  2048. fi
  2049. if test -f 'trace.c' -a "${1}" != "-c" ; then 
  2050.   echo shar: Will not clobber existing file \"'trace.c'\"
  2051. else
  2052. echo shar: Extracting \"'trace.c'\" \(1031 characters\)
  2053. sed "s/^X//" >'trace.c' <<'END_OF_FILE'
  2054. X/***********************************************************************
  2055. X * $Author: markv $
  2056. X * $Revision: 1.2 $
  2057. X * $Date: 88/09/12 13:01:15 $
  2058. X * $Log:    trace.c,v $
  2059. X * Revision 1.2  88/09/12  13:01:15  markv
  2060. X * Fixed Trace to call Intersect with the max dist argument of HUGE.
  2061. X * 
  2062. X * Revision 1.1  88/09/11  11:00:45  markv
  2063. X * Initial revision
  2064. X * 
  2065. X ***********************************************************************/
  2066. X
  2067. X#include <stdio.h>
  2068. X#include <math.h>
  2069. X#include "defs.h"
  2070. X#include "extern.h"
  2071. X
  2072. XTrace(level, weight, ray, color) 
  2073. X int level;
  2074. X Flt weight;
  2075. X Ray *ray ;
  2076. X Color color ;
  2077. X{
  2078. X    Object *prim ;
  2079. X    Vec P, N ;
  2080. X    Isect hit ;
  2081. X
  2082. X    if (level >= maxlevel) {
  2083. X        color[0] = color[1] = color[2] = 0.0 ;
  2084. X        return ;
  2085. X    }
  2086. X        
  2087. X    nRays ++ ;
  2088. X
  2089. X    if (Intersect(ray, &hit, HUGE)) {
  2090. X        prim = hit.isect_prim ;
  2091. X        RayPoint(ray, hit.isect_t, P);
  2092. X        (*prim -> o_procs -> normal) (prim, &hit, P, N);
  2093. X        if ((VecDot(ray->D, N)) >= 0.0) {
  2094. X            VecNegate(N);
  2095. X        }
  2096. X        Shade(level, weight, P, N, ray -> D, &hit, color);
  2097. X    } else {
  2098. X        VecCopy(BackgroundColor, color) ;
  2099. X    }
  2100. X}
  2101. END_OF_FILE
  2102. if test 1031 -ne `wc -c <'trace.c'`; then
  2103.     echo shar: \"'trace.c'\" unpacked with wrong size!
  2104. fi
  2105. # end of 'trace.c'
  2106. fi
  2107. if test -f 'vector.c' -a "${1}" != "-c" ; then 
  2108.   echo shar: Will not clobber existing file \"'vector.c'\"
  2109. else
  2110. echo shar: Extracting \"'vector.c'\" \(1707 characters\)
  2111. sed "s/^X//" >'vector.c' <<'END_OF_FILE'
  2112. X/***********************************************************************
  2113. X * $Author: markv $
  2114. X * $Revision: 1.1 $
  2115. X * $Date: 88/09/11 11:00:46 $
  2116. X * $Log:    vector.c,v $
  2117. X * Revision 1.1  88/09/11  11:00:46  markv
  2118. X * Initial revision
  2119. X * 
  2120. X ***********************************************************************/
  2121. X#include <stdio.h>
  2122. X#include <math.h>
  2123. X#include "defs.h"
  2124. X#include "extern.h"
  2125. X
  2126. XFlt 
  2127. XVecNormalize(vec)
  2128. X Vec vec ;
  2129. X{
  2130. X    Flt len ;
  2131. X    len = (Flt) VecLen(vec);
  2132. X    vec[0]/=len ;
  2133. X    vec[1]/=len ;
  2134. X    vec[2]/=len ;
  2135. X    return(len) ;
  2136. X}
  2137. X
  2138. X#ifdef DUMB_CPP
  2139. X/*
  2140. X * Some machines can't handle all the vector operations, so if we define
  2141. X * DUMB_CPP, we replace them with equivalent function calls...
  2142. X */
  2143. X
  2144. XMakeVector(x, y, z, v)
  2145. X Flt x, y, z ;
  2146. X Vec v ;
  2147. X{
  2148. X    v[0] = x ; v[1] = y ; v[2] = z ;
  2149. X}
  2150. X
  2151. XVecNegate(v)
  2152. X Vec v ;
  2153. X{
  2154. X    v[0] = -v[0] ;
  2155. X    v[1] = -v[1] ;
  2156. X    v[2] = -v[2] ;
  2157. X}
  2158. X
  2159. XFlt 
  2160. XVecDot(a, b)
  2161. X Vec a, b ;
  2162. X{
  2163. X    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] ;
  2164. X}
  2165. X
  2166. XFlt
  2167. XVecLen(a)
  2168. X Vec a;
  2169. X{
  2170. X    return sqrt(VecDot(a, a)) ;
  2171. X}
  2172. X
  2173. XVecCopy(a, b) 
  2174. X Vec a, b ;
  2175. X{
  2176. X    b[0] = a[0] ;
  2177. X    b[1] = a[1] ;
  2178. X    b[2] = a[2] ;
  2179. X}
  2180. X
  2181. XVecAdd(a, b, c)
  2182. X Vec a, b, c ;
  2183. X{
  2184. X    c[0] = a[0] + b[0] ;
  2185. X    c[1] = a[1] + b[1] ;
  2186. X    c[2] = a[2] + b[2] ;
  2187. X}
  2188. X
  2189. XVecSub(a, b, c)
  2190. X Vec a, b, c ;
  2191. X{
  2192. X    c[0] = a[0] - b[0] ;
  2193. X    c[1] = a[1] - b[1] ;
  2194. X    c[2] = a[2] - b[2] ;
  2195. X}
  2196. X
  2197. XVecComb(A, a, B, b, c)
  2198. X Flt A, B ;
  2199. X Vec a, b, c ;
  2200. X{
  2201. X    c[0] = A * a[0] + B * b[0] ;    
  2202. X    c[1] = A * a[1] + B * b[1] ;    
  2203. X    c[2] = A * a[2] + B * b[2] ;    
  2204. X}
  2205. X
  2206. XVecAddS(A, a, b, c)
  2207. X Flt A ;
  2208. X Vec a, b, c ;
  2209. X{
  2210. X    c[0] = A * a[0] + b[0] ;    
  2211. X    c[1] = A * a[1] + b[1] ;    
  2212. X    c[2] = A * a[2] + b[2] ;    
  2213. X}
  2214. X
  2215. XVecCross(a, b, c)
  2216. X Vec a, b, c ;
  2217. X{
  2218. X    c[0] = a[1] * b[2] - a[2] * b[1] ;
  2219. X    c[1] = a[2] * b[0] - a[0] * b[2] ;
  2220. X    c[2] = a[0] * b[1] - a[1] * b[0] ;
  2221. X}
  2222. X
  2223. X#endif /* DUMB_CPP */
  2224. END_OF_FILE
  2225. if test 1707 -ne `wc -c <'vector.c'`; then
  2226.     echo shar: \"'vector.c'\" unpacked with wrong size!
  2227. fi
  2228. # end of 'vector.c'
  2229. fi
  2230. echo shar: End of archive 1 \(of 3\).
  2231. cp /dev/null ark1isdone
  2232. MISSING=""
  2233. for I in 1 2 3 ; do
  2234.     if test ! -f ark${I}isdone ; then
  2235.     MISSING="${MISSING} ${I}"
  2236.     fi
  2237. done
  2238. if test "${MISSING}" = "" ; then
  2239.     echo You have unpacked all 3 archives.
  2240.     rm -f ark[1-9]isdone
  2241. else
  2242.     echo You still need to unpack the following archives:
  2243.     echo "        " ${MISSING}
  2244. fi
  2245. ##  End of shell archive.
  2246. exit 0
  2247.  
  2248.